class Solution:

    def countSubstrings(self, s: str) -> int:
        n = len(s)
        dp = [[False] * n for _ in range(n)]
        ans = 0
        for i, v in enumerate(s):
            for j in range(i, -1, -1):
                if i == j or (v == s[j] and (i == j + 1 or dp[j + 1][i - 1])):
                    dp[j][i] = True
                    ans += 1
        return ans


s = Solution()
print(s.countSubstrings("aabbccbbccaa"))
print(s.countSubstrings(s="aaa"))
print(s.countSubstrings(s="abc"))

print(len('04197c2476ca1e2f6d912e9077d62f60'))
